package com.feishi.core.util.common;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

/**
 * @version 1.0
 * @auth caixq
 * @time 18-3-8 09:16
 **/
@SuppressWarnings("unchecked")
public class OrderUtil {
    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new FileReader("/home/caixq/project/shell/out"));
        TreeNode node = null;
        int i=0;
        long start=System.currentTimeMillis();
        do{

            if(i++<1){
                continue;
            }
            if(i>5000000){
                break;
            }
            if (node==null){
                node=new TreeNode(Integer.parseInt(br.readLine()));
            }else{
                node.insert(Integer.parseInt(br.readLine()));
            }
        }while(br.read()!=-1);
        System.out.println(node.array().size());
        System.out.println("time="+(System.currentTimeMillis()-start));

    }
    public static class TreeNode<T extends Comparable<T>>{
        TreeNode<T> parent;
        TreeNode<T> left;
        TreeNode<T> right;
        T data;

        public TreeNode(T data) {
            this.data = data;
        }

        public TreeNode(TreeNode<T> parent, T data) {
            this.parent = parent;
            this.data = data;
        }

        public void insert(T t){
            int status=t.compareTo(data)<=0?0:1;
            switch (status){
                case 0:
                    if(left==null){
                        left=new TreeNode<T>(this,t);
                    }else {
                        left.insert(t);
                    }
                    break;
                case 1:
                    if(right==null){
                        right=new TreeNode<T>(this,t);
                    }else {
                        right.insert(t);
                    }
                    break;

            }
        };

        public List<T> array() {
            List<T> result=new ArrayList<>();
            result.add(data);
            if(left!=null){
                result.addAll(0,left.array());
            }
            if(right!=null){
                result.addAll(right.array());
            }

            return result;
        }
        public static <T extends Comparable<T>> List<T> array(TreeNode treeNode) {
            List<T> result=new ArrayList<>();
            TreeNode<T> currentNode = null;
            TreeNode<T> nextNode=null;
            while (treeNode.left!=null){
                nextNode=treeNode.left;
            }
            int from=0;
           out: while (true){
               currentNode=nextNode;
               result.add(nextNode.data);
                switch (from){
                    case 0: {

                        if(currentNode.parent==null){
                            if(currentNode.right==null){
                                break out;
                            }else{

                            }
                        }else {

                        }
                    }break;
                }
            }

            return result;
        }
    }
}
